package cn.edu.zufe.mjt.dfs;

import cn.edu.zufe.mjt.graph.GraphStorage;

import java.util.List;
import java.util.Scanner;

/**
 * 深度优先搜索——连通块统计
 * 给你一个无向图，请你统计出图中所有连通块的数量。
 * 连通块指的是图中由任意两个顶点组成的子图，且子图中任意两个顶点之间都有路径相连。
 * 请你返回连通块的数量。
 * 输入：
 * 第一行包含两个整数 n 和 m，表示图中有 n 个顶点和 m 条边。
 * 接下来 m 行，每行包含两个整数 u 和 v，表示存在一条从顶点 u 到顶点 v 的边。
 * 输出：
 * 一个整数，表示图中所有连通块的数量。
 * 样例输入：
 * 5 4
 * 1 2
 * 2 3
 * 3 4
 * 4 5
 * 样例输出：
 * 1
 */
public class UnicomBlock {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        int m = scanner.nextInt();
        int[][] graph = new int[n][n];
        for (int i = 0; i < m; i++) {
            int u = scanner.nextInt() - 1;
            int v = scanner.nextInt() - 1;
            graph[u][v] = 1;
            graph[v][u] = 1;
        }
        int count = 0;
        boolean[] visited = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                dfs(graph, visited, i);
                count++;
            }
        }
        System.out.println(count);

        // 邻接表存储
        List<List<Integer>> lists = GraphStorage.generateAdjList(graph);
        int count2 = 0;
        boolean[] visited2 = new boolean[n];
        for (int i = 0; i < n; i++) {
            if (!visited2[i]) {
                dfs(lists, visited2, i);
                count2++;
            }
        }
        System.out.println(count2);
    }

    private static void dfs(List<List<Integer>> lists, boolean[] visited, int i) {
        visited[i] = true;
        for (int j : lists.get(i)) {
            if (!visited[j]) {
                dfs(lists, visited, j); // 邻居未访问过，递归访问
            }
        }
    }

    private static void dfs(int[][] graph, boolean[] visited, int i) {
        visited[i] = true;
        for (int j = 0; j < graph.length; j++) {
            if (graph[i][j] == 1 && !visited[j]) {
                dfs(graph, visited, j); // 邻居未访问过，递归访问
            }
        }
    }
}
